#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#define MAXDATA 100000  //大于堆中所有可能元素的值
#define MINDATA 0     //小于堆中所有可能元素的值
#define EROOR -1      //堆中不可能出现的值
typedef int ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;  
    BinTree Right; 
};

typedef int ElementType;

typedef struct HNode *Heap;
//堆
struct HNode{
    ElementType *Data;//存储元素的数组
    int Size; //堆中当前元素个数 
    int Capacity;  //堆的最大容量 
};
typedef Heap MaxHeap; //最大堆
typedef Heap MinHeap; //最小堆

//创建容量为Maxsize的最大堆
MaxHeap CreateMaxHeap(int MaxSize){
    MaxHeap H = (MaxHeap)malloc(sizeof(struct HNode));
    H->Data = (ElementType*)malloc(sizeof(ElementType)*(MaxSize+1));//从a[1]开始保存数 所以数组数量要+1
    H->Size = 0;
    H->Capacity=MaxSize;
    H->Data[0] = MAXDATA;
    return H;
}
//创建容量为Maxsize的最小堆
MinHeap CreateMinHeap(int MaxSize){
    MinHeap H = (MinHeap)malloc(sizeof(struct HNode));
    H->Data = (ElementType*)malloc(sizeof(ElementType)*(MaxSize+1));//从a[1]开始保存数 所以数组数量要+1
    H->Size = 0;
    H->Capacity=MaxSize;
    H->Data[0] = MINDATA;
    return H;
}
bool IsFull(MaxHeap H)
{
    return(H->Size == H->Capacity);
}
//最大堆的插入
bool InsertMax(MaxHeap H, ElementType x){
    if(IsFull(H)){
        printf("Maxheap is full");
    }
    int i = ++H->Size;//i指向插入后堆中的最后一个元素的位置
    for (; H->Data[i/2]<x; i/=2) {
//此处的判断 如果向上到了a[1]还没停止的话 需要让其就停在a[1]处 所以要在a[0]的位置放置一个"岗哨"
//这个岗哨对于最大堆来说要放入一个 比数组中所有数都大的数 这样在比较a[0]和x时 a[0]>x 循环就会停下来
        H->Data[i] = H->Data[i/2];   //上滤X
    }
    H->Data[i] = x;//将x插入
    return true;
}
//最小堆的插入
bool InsertMin(MinHeap H, ElementType x){
    if(IsFull(H)){
        printf("Minheap is full");
    }
    int p = ++H->Size;
    for (; H->Data[p/2]>x; p/=2) {
//这里是最小堆  所以在a[0]位置的岗哨保存了比数组中所有元素都小的元素
        H->Data[p] = H->Data[p/2];
    }
    H->Data[p] = x;
    return true;
}
bool IsEmpty(MaxHeap H)
{
    return(H->Size==0);
}
//最大堆的删除
ElementType DeleteMax(MaxHeap H){//从最大堆中取出键值为最大的元素，并删除一个节点
    if(IsEmpty(H)){
        printf("Maxheap is empty");
        return EROOR;
    }
    ElementType top = H->Data[1];//堆顶元素(最大)
    ElementType x = H->Data[H->Size--];
    int parent = 1;
    int child;
    for (; parent*2<=H->Size; parent=child) {
        child = 2*parent;//左子节点
        //查找是否有右子节点 并且 右子节点的元素大于左子节点
        if ((child!=H->Size) && (H->Data[child]<H->Data[child+1])) {
            child++;//右子节点
            if (x<H->Data[child]) {
                H->Data[parent] = H->Data[child];
            }else{//找到了位置
                break;
            }
        }
    }
    H->Data[parent] = x;
    return top;
}
//最小堆的删除
ElementType DeleteMin(MinHeap H){
    if(IsEmpty(H)){
        printf("Maxheap is empty");
        return EROOR;
    }
    ElementType top = H->Data[1];
    ElementType x = H->Data[H->Size--];
    int parent,child;
    for (parent = 1; parent*2<H->Size; parent=child) {
        child = parent*2;
            //注意这里是存在右子节点 并且 右子节点比左子节点小    
        if (child!=H->Size && H->Data[child] > H->Data[child+1]) {
            child++;
            //如果比右子节点还小
            if (H->Data[child]>=x) {
                break;
            }else{//下滤
                H->Data[parent] = H->Data[child];
            }
        }
    }
    H->Data[parent] = x;
    return top;
}
void PercDownMax(MaxHeap H, int n){
    int parent,child;
    ElementType x;
    x = H->Data[n];//取出父根节点存放的值
    //向下过滤
    for (parent = n; parent*2<H->Size; parent=child) {
        child = 2*parent;
        if ((child!=H->Size) && (H->Data[child]<H->Data[child+1])) {
            child++;
            if (H->Data[child]<=n) {
                break;
            }else
                H->Data[child] = H->Data[parent];
        }
    }
    H->Data[parent] = x;
}
 
void BuildMaxHeap(MaxHeap H){
    int i;
    for (i=H->Size/2; i>0; i--) { //从最后一个父节点开始
        PercDownMax(H, i);
    }
}
void PercDownMin(MinHeap H, int n){
    int parent,child;
    ElementType x;
    x = H->Data[n];//取出父根节点存放的值
    //向下过滤
    for (parent = n; parent*2<H->Size; parent=child) {
        child = 2*parent;
        if ((child!=H->Size) && (H->Data[child]>H->Data[child+1])) {
            child++;
            if (H->Data[child]>=n) {
                break;
            }
            else
                H->Data[child] = H->Data[parent];
        }
    }
    H->Data[parent] = x;
}
 
void BuildMinHeap(MinHeap H){
    int i;
    for (i=H->Size/2; i>0; i--) { //从最后一个父节点开始
        PercDownMin(H, i);
    }
}

typedef struct Node{
    int *Data;
    int MaxSize;  //容量
    int Top; //栈顶
}Node,*Stack;

Stack CreatStack(int Max)
{
    Stack S = (Stack)malloc(sizeof(Node));
    S->Data = (int *)malloc(Max * sizeof(int));
    S->MaxSize = Max;
    S->Top = -1;
    return S;
}
int IsFull(Stack S)
{
    return S->Top == S->MaxSize - 1;
}

bool Push(Stack S,int x)
{
    if (IsFull(S)){
        printf("stack is full");
        return false;
    }
    else
    {
        S->Top=S->Top+1;
        S->Data[S->Top]=x;
        return true;
    }
}

bool IsEmpty(Stack S)
{
    return (S->Top == -1);
}

void Pop(Stack S)
{
    if (IsEmpty(S))
        printf("stack is empty");
    else
        S->Top--;
}
int Top(Stack S)
{
    if (IsEmpty(S))
        printf("stack is empty");
    else
        return S->Data[S->Top];
}
int pop(Stack S)
{ 	   
    if (IsEmpty(S))
        printf("Invalid");
    return S->Data[S->Top--];
}
int wu(MaxHeap H){
    return H->Data[1];
}


int main(){
    MaxHeap A1=CreateMaxHeap(MAXDATA);
    MinHeap A2=CreateMinHeap(MAXDATA);
    Stack S=CreatStack(MAXDATA);
    int H[MAXDATA],P[MAXDATA];
    int N,i,j,max,min;
    scanf("%d",&N);
    for(i=0;i<N,i++)
    {
        char t[11];
        scanf("%s",t);

        if(t[1]=='u'){
            int x,y;
            scanf("%d",&x);
            Push(S,x);
            y=wu(A1);
            if(x>y){
                InsertMin(A2,x);
                max++;
                H[i]=1;
            } 
            else{
                InsertMax(A1,x);
                min++;
                H[i]=0;
            }
            if(max>min){
                if(max-min>1){
                    int z=DeleteMax(A1);
                    InsertMin(A2,z);
                    H[i]=1;
                }
            }
            if(max<min){
                if(min-max>1){
                    int z=DeleteMin(A2);
                    InsertMax(A1,z);
                    H[i]=0;
                }
            }
        }

        else if(t[1]=='o'){
            int x=pop(S);
            printf("%d\n",x);
            
        }
        
        else if(t[1]=='e'){
            PeekMedian;
        }
    }
    
    return 0;
}